﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BinaryTreeCode
{
    //====================== 递归遍历
    //如何写出正确的递归算法
    //1.确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数，
    //                           并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型
    //2.确定终止条件：如果递归没有终止，操作系统的内存栈必然会溢出
    //3.确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里就会重复调用自己来实现递归的过程
    class RecursiveTraversal
    {
        //=================二叉树的遍历
        public IList<int> PreorderTraversal(TreeNode root )
        {
            IList<int> result = new List<int>();
            Traversal(root, result);
            return result;
        }

        //=================力扣144 前序遍历
        //给你二叉树的根节点root，返回它的节点值的前序遍历
        private void Traversal(TreeNode cur, IList<int> vec)
        {
            if (cur == null)
                return;

            vec.Add(cur.val);//中
            Traversal(cur.left, vec);//左
            Traversal(cur.right, vec);//右
        }

        //=================力扣94 中序遍历
        //给你二叉树的根节点root，返回它的节点值的中序遍历
        private void Traversal_2(TreeNode cur, IList<int> vec)
        {
            if (cur == null)
                return;
            Traversal_2(cur.left, vec);//左
            vec.Add(cur.val);           //中
            Traversal_2(cur.right, vec);//右
        }

        //================力扣145 后序遍历
        //给定一个二叉树，返回它的 后序 遍历。
        private void Traversal_3(TreeNode cur, IList<int> vec)
        {
            if (cur == null)
                return;
            Traversal_3(cur.left, vec);//左
            Traversal_3(cur.right, vec);//右
            vec.Add(cur.val);           //中
        }
    }
}
